#include <bits/stdc++.h>
#include <string>
using namespace std;

enum HashStatus
{
    Remove = -1, // 余温
    Acitved = 1, // 有人
    Empty = 0    // 空
};

struct HashMap
{
    int *data;          // 散列数组
    int size;           // 散列容量
    HashStatus *status; // 散列数组状态
    int remain;         // 剩余容量
};

// 创建一个散列
struct HashMap *createHashMap(int size)
{
    struct HashMap *h = (struct HashMap *)malloc(sizeof(struct HashMap));
    h->size = h->remain = size;
    h->data = (int *)malloc(sizeof(int) * size);
    h->status = (HashStatus *)malloc(sizeof(HashStatus) * size);
    for(int i=0;i<size;i++){
        h->status[i] = Empty;
    }
    return h;
}

// 散列函数 (灵活的) 获取数的索引
int getHashIndex(struct HashMap *h, int val)
{
    return val % h->size;
}

// 向散列里插入一个数
void insertHash(struct HashMap *h, int val)
{
    if (h->remain == 0)
        return;
    int index = getHashIndex(h, val);
    while (h->status[index] == Acitved)
    {
        index = (index + 1) % h->size;
    }
    h->data[index] = val;
    h->remain--;
    h->status[index] = Acitved;
}

// 寻找一个数再散列里的索引
int findHashVal(struct HashMap *h, int val)
{
    int pos, index;
    pos = index = getHashIndex(h, val);
    while (1)
    {
        if (h->data[index] == val && h->status[index] == Acitved)
        {
            pos = index;
            break;
        }
        index = (index + 1) % h->size;
        if (index == pos)
            return -1;
    }
    return pos;
}

void deleteHash(struct HashMap *h, int val)
{
    int pos = findHashVal(h, val);
    if (pos == -1)
        return;
    h->status[pos] = Remove;
    h->remain++;
}

void printHash(struct HashMap *h)
{
    for (int i = 0; i < h->size; i++)
    {
        printf("%4d",i);
    }
    cout << endl;
    for (int i = 0; i < h->size; i++)
    {
        if (h->status[i] == Empty)
            cout << "   -";
        else if (h->status[i] == Remove)
            cout << "   X";
        else printf("%4d",h->data[i]);   
    }
    cout << endl;
}

int main()
{
    struct HashMap *h = createHashMap(11);
    // 5 16 10 21 33 9 20
    insertHash(h, 5);
    insertHash(h, 16);
    insertHash(h, 10);
    insertHash(h, 21);
    insertHash(h, 33);
    insertHash(h, 9);
    insertHash(h, 20);
    printHash(h);
    deleteHash(h,21);
    printHash(h);
    return 0;
}
